#include <iostream>

using namespace std;

#define MAX_LEN 100

template<class T>
void maxSubArr(T *arr, int len, int &start, int &end, T &max_sum)
{
    if(len <= 0)
        return;

    T max_ending_sum;
    int i, starts[MAX_LEN]/*the start of the max sub array end with a[i]*/;

    max_ending_sum = arr[0];
    max_sum = arr[0];
    start = 0;
    end = 0;
    starts[0] = 0;
    for(i = 1; i < len; i ++)
    {
        // max_ending_sum here refers to the maximum subarray length ends with element a[i - 1]
        if(max_ending_sum + arr[i] > arr[i])
        {
            max_ending_sum = max_ending_sum + arr[i];
            starts[i] = starts[i - 1];
        }
        else
        {
            max_ending_sum = arr[i];
            starts[i] = i;
        }

        // max_ending_sum now refers to the maximum subarray length ends with element a[i]
        if(max_ending_sum > max_sum)
        {
            max_sum = max_ending_sum;
            start = starts[i];
            end = i;
        }
    }
}

int main()
{
    //int a[] = {1, -2, 3, 10, -4, 7, 2, -5};
    //int len = 8;
    int a[] = {-1, -2, -3, -10, -4, -7, -2, -5};
    int len = 8;
    int start, end, max_sum, i;

    maxSubArr(a, len, start, end, max_sum);

    cout << "maximum summary : " << max_sum << endl;
    cout << "the subarray : ";
    for(i = start; i <= end; i ++)
    {
        cout << a[i] << " ";
    }
}
